package com.kevinkk.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
 * 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
 * 返回一个表示每个字符串片段的长度的列表。
 */

public class PartitionLabels {
    class Solution {
        public List<Integer> partitionLabels(String s) {
            int[] count = new int[26];
            char[] c = s.toCharArray();
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < c.length; i++) {
                count[c[i] - 'a'] = i;
            }
            for (int i = 0, start = 0, cover = 0; i < c.length; i++) {
                // 设置一个 cover
                cover = Math.max(count[c[i] - 'a'], cover);
                if (i == cover) {
                    res.add(i - start + 1);
                    start = i + 1;
                }
            }
            return res;
        }
    }
}
